/*
 * @lc app=leetcode.cn id=17 lang=cpp
 *
 * [17] 电话号码的字母组合
 *
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/
 *
 * algorithms
 * Medium (57.75%)
 * Likes:    1870
 * Dislikes: 0
 * Total Accepted:    474K
 * Total Submissions: 820.9K
 * Testcase Example:  '"23"'
 *
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：digits = ""
 * 输出：[]
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 0 <= digits.length <= 4
 * digits[i] 是范围 ['2', '9'] 的一个数字。
 * 
 * 
 */

// @lc code=start
class Solution {
// private:
//     const string letterMap[10] = {
//         "", // 0
//         "", // 1
//         "abc", // 2
//         "def", //3
//         "ghi", //4
//         "jkl", //5
//         "mno", //6
//         "pqrs", //7
//         "tuv", //8
//         "wxyz", //9
//     };

//     void backtracking(const string& digits, int index, const string& path, vector<string>& res) {
//         if(index == digits.size()) {
//             res.push_back(path);
//             return;
//         }

//         int digit = digits[index] - '0';
//         string letters = letterMap[digit];

//         for(int i = 0; i < letters.size(); i++) {
//             backtracking(digits, index + 1, path + letters[i], res);
//         }
//     }

// public:
//     vector<string> letterCombinations(string digits) {
//         vector<string> res = {};
//         if(digits.size() == 0) return res;
//         backtracking(digits, 0, "", res);
//         return res;
//     }

private:
    const vector<string> letterMap = {
    // const string letterMap[10] = {
        "", //0
        "", //1
        "abc", //2
        "def", //3
        "ghi", //4
        "jkl", //5
        "mno", //6
        "pqrs", //7
        "tuv", //8
        "wxyz" //9
    };
    vector<string> res;
    // // 非常量引用不能引用临时变量，但是常量引用可引用临时变量
    // void backtracking(string digits, int index, string&  path) {  /////达咩！！！！！！！！！！

    // void backtracking(string digits, int index, string path) {
    void backtracking(string digits, int index, const string& path) {
        // if(path.size() == digits.size()) {  // 二选一
        if(index == digits.size()) {         // 二选一
            res.push_back(path);
            return;
        }

        int digit = digits[index] - '0';
        string letter = letterMap[digit];

        for(int i = 0; i < letter.size(); i++) {

            backtracking(digits, index + 1, path + letter[i]);

        }
    }

public:
    vector<string> letterCombinations(string digits) { 
        res.clear();
        if(digits.size() == 0) return res;
        backtracking(digits, 0, "");
        return res;
    }

};
// @lc code=end

